Conventional techniques that use differential concepts to reconstruct surfaces from scanned data point sets typically assume a finite set of points that are sampled on the surface of a shape in a three-dimensional space and ask for an approximation of that surface. Such techniques may be classified by the assumptions they make about the data point sets. Techniques that make structural assumptions may simplify the reconstruction task by providing the points in a specific order. Techniques that make density assumptions may enable the application of differential concepts by providing sufficiently many point samples within each data point set. Techniques that avoid assumptions typically require the reconstruction operations to rely on general principles of describing geometric shapes.
One conventional technique that incorporates density assumptions is described in an article by H. Hoppe et al., entitled “Surface Reconstruction from Unorganized Points,” Computer Graphics, Proceedings of SIGGRAPH, pp. 71–78 (1992). This technique uses normal estimates to generate a signed distance function from which a surface is extracted as a zero-set. Another conventional technique is described in an article by N. Amenta et al., entitled “Surface Reconstruction by Voronoi Filtering,” Discrete Computer Geometry, Vol. 22, pp. 481–504 (1999). This technique exploits shape properties of three-dimensional Voronoi cells for densely sampled data points. Unfortunately, because these reconstruction techniques rely heavily on the quality of the data, they may fail if a given data point set does not adequately support the application of differential concepts. For example, these reconstruction techniques may fail if there are large gaps in the distribution of the data points in a set or if the accuracy of the data points is compromised by random noise. These techniques may also fail if the data point sets are contaminated by outliers. Data point sets having relatively large gaps, high levels of random noise and/or outliers may result from scanning objects having sharp edges and corners.
Additional surface reconstruction techniques can be distinguished based on the internal operations they perform. For example, in “sliced data” reconstruction techniques, the data points and their ordering are assumed to identify polygonal cross-sections in a finite sequence of parallel planes. This assumption may simplify the complexity of the technique, but it also typically limits the technique to data generated by a subclass of scanners. A survey of work that includes this technique is described in an article by D. Meyers et al., entitled “Surfaces from Contours,” ACM Trans. on Graphics, Vol. 11, pp. 228–258 (1992). In another reconstruction technique, the data points are used to construct a map f: 3→, and the surface is constructed as the zero set, f−1(0). The zero set may be constructed using a marching cube algorithm that is described in an article by W. Lorensen et al., entitled “Marching Cubes: A High Resolution 3D Surface Construction Algorithm,” Computer Graphics, Proceedings of SIGGRAPH, Vol. 21, pp. 163–169 (1987). One example of this reconstruction technique is described in the aforementioned article by H. Hoppe et al. Attempts to generalize and apply surface meshing techniques to the reconstruction of surfaces from unstructured data point sets have also been presented in a survey paper by S. K. Lodha and R. Franke, entitled “Scattered Data Techniques for Surfaces,” Proceedings of a Dagstuhl Seminar, Scientific Visualization Dagstuhl '97, Hagen, Nielson and Post (eds.), pp. 189–230. Additional techniques for automatically wrapping data point sets into digital models of surfaces are also disclosed in U.S. Pat. No. 6,377,865 to Edelsbrunner et al., entitled “Methods of Generating Three-Dimensional Digital Models of Objects by Wrapping Point Cloud Data Points,” assigned to the present assignee, the disclosure of which is hereby incorporated herein by reference.